#include <stdio.h>
#include <stdbool.h>

int CheckInsertionSort(int a[],int b[],int n);
void Do1MoreInsertionSort(int b[],int n,int nextCard);
void prtArr(int b[],int n);
void Do1MoreHeapSort(int b[],int n);
int main(){
	int n,ret;
	scanf("%d",&n);
	int a[n],b[n];
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	for(int i=0;i<n;i++)scanf("%d",&b[i]);
	ret=CheckInsertionSort(a,b,n);
	if( -1 != ret ){
		printf("Insertion Sort\n");
		Do1MoreInsertionSort(b,n,ret);
		prtArr(b,n);
	}else{
		printf("Heap Sort\n");
		Do1MoreHeapSort(b,n);
		prtArr(b,n);
	}
}

int CheckInsertionSort(int a[],int b[],int n){
	int i=1,ret;
	for(; b[i-1] <= b[i] ; i++){}
	ret=i;
	for(; i<n && (a[i]==b[i]) ; i++){}
	if( i == n )
		return ret;
	else
		return -1;
}

void Do1MoreInsertionSort(int b[],int n,int nextCard){
	int tmp=b[nextCard];
	int i=nextCard-1;
	for(;i>=0;i--){
		if( b[i]> tmp ){
			b[i+1]=b[i];
		}else{
			break;
		}
	}
	b[i+1]=tmp;
	return;
}
void prtArr(int b[],int n){
	int i;
	for(i=0;i<n-1;i++)
		printf("%d ",b[i]);
	printf("%d",b[i]);
	return;
} 
void Do1MoreHeapSort(int b[],int n){
	int t=b[0];
	int p;
	for(p=n-1;b[p] >= t;p--){}
	b[0]=b[p];
	b[p--]=t;
	t=b[0];
	int i=0;
	while( 2*i+1 <= p ){
		if( 2*i+1 < p && b[2*i+2] > b[2*i+1] && b[2*i+2] > t ){
			b[i]=b[2*i+2];
			i=2*i+2;
		}else if( b[2*i+1] > t ){
			b[i]=b[2*i+1];
			i=2*i+1;
		}else{
			break;
		}
	}
	b[i]=t;
	return;
}
